리스트?

컴퓨터에서 다루는 가장 많은 데이터 유형이 리스트.
(Set집합은 컴퓨터과학에서는 거의 다루지 않는다고 한다.)

배열 array

가장 먼저 접하는 리스트의 유형.
배열 안에 int 5개를 넣은것과 개별 변수 5개를 가지고있는것의 차이는?
배열에는 int간의 순서가 있지만 개별 변수에는 없다.
'순서'라는 것도 현실세계에 존재하는 반영되어야할 속성이기 때문에 배열이 필요하게 되는것이다.

장점은 배열이 담겨있는 요소에 접근하는데 일정 시간(상수 시간)이 걸린다는 것이다.
배열이 있는 메모리에 찾아가서 안에 있는 변수들을 찾는데 대략 5-6ns(nano second)가 걸린다고.
(배열의) 기본 주소 + offset이 변수의 위치.
offset이란 데이터형에 따라 정해진 크기 size에 그 순서인 index를 곱한것.
기본 주소 + (size * index) 를 계산해서 배열에 담긴 변수를 찾는다.

단점은 배열의 크기를 미리 알고 지정해야한다는('정적'이라는) 것.
그리고 특정 위치에 요소를 삽입하려면 기존 항목들을 이동해야 한다. 그러니까 a,b,d,e,f,.... 사이에 c를 넣으려면 d부터 뒤에 있는 모든것들을 한칸씩 미루고 c를 넣어야 한다.

연결 리스트 Linked List

연속되는 항목들이 있고 앞의 요소가 뒤의 요소를 포인터로 연결한다.

배열은 미리 크기가 지정되면서 메모리 한곳에 다 같이 위치하지만, 연결리스트는 메모리 상에 위치가 서로 붙어있지 않아서, 항상 일정한 시간이 걸리지 않는다.
배열은 아파트처럼 같은 동 안에 모든 호수다 이웃하고 있다면, 연결 리스트는 그렇지 않다는 것이다.

그러면 연결리스트는 특정 순서에 위치한 요소를 찾을때 어떻게 접근하나?

예를들어 5번째 에 있는 변수를 찾으려면 0번째에 가서 포인터를 읽고 1번째에 가서 포인터를 읽고 2번째에 가서 ..... 그렇게 반복해야되나?

배열의 다른 단점인 특정 위치에 요소를 삽입하기 어려운 문제를 연결 리스트는 포인터를 바꾸는 것으로 쉽게 해결 가능하다. a->b->d->e->... 에서 c를 추가한다면 메모리 아무 위치에 c가 추가되고 b가 가지고 있는 포인터를 c의 위치를 가리키도록 하고 원래 b가 가리키던 d의 위치를 c가 가리킨다.